package william.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ZhangShenao
 * @date 2024/1/16
 * @description <a href="https://leetcode.cn/problems/symmetric-tree/description/">...</a>
 */
public class Leetcode101_对称二叉树 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 采用递归算法
     * 判断以root为根的二叉树是否对称,需要同时满足以下几个条件:
     * -1.root.left和root.right同时为null,或二者值相等
     * -2.root.left.left和root.right.right对称
     * -3.root.left.right和root.right.left对称
     * <p>
     * 时间复杂度O(N) 两棵树各遍历一次
     * 空间复杂度O(logN) 递归栈深度=树高度
     */
    public boolean isSymmetric(TreeNode root) {
        //边界条件校验
        if (root == null) {
            return true;
        }

        //调用递归算法
        return isSymmetricRecursive(root.left, root.right);
    }

    /**
     * 递归算法
     * 判断以left为根和以right为根的两棵树是否对称
     */
    private boolean isSymmetricRecursive(TreeNode left, TreeNode right) {
        if (left == null && right == null) {    //递归终止条件
            return true;
        }
        if (left == null || right == null) { //两棵树结构不同,非对称
            return false;
        }
        if (left.val != right.val) { //两棵树节点值不同,非对称
            return false;
        }

        //递归校验:left.left和right.right对称 && left.right和right.left对称
        return (isSymmetricRecursive(left.left, right.right) && isSymmetricRecursive(left.right, right.left));
    }

    /**
     * 迭代实现: 借助队列
     * Step1: 将根节点的左、右子节点入队
     * Step2: 将队列中的节点成对出队
     * Step3: 比较每次出队的两个节点
     * Step4: 依次将两个节点的{left.left,right.right}以及{left.right,right.left}成对入队
     * Step5: 循环上述过程,直到队列为空
     */
    private boolean isSymmetricIteration(TreeNode root) {
        //借助一个队列
        Queue<TreeNode> queue = new LinkedList<>();

        //首先将左、右两个子节点入队
        queue.offer(root.left);
        queue.offer(root.right);

        //迭代实现
        while (!queue.isEmpty()) {
            //每次成对出队两个节点
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();

            //首先比较两个节点的值是否相等
            if (left == null && right == null) {
                continue;
            }
            if (left == null || right == null) {
                return false;
            }
            if (left.val != right.val) {
                return false;
            }

            //依次将两个节点的{left.left,right.right}以及{left.right,right.left}成对入队
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }

        //迭代结束,队列为空,满足对称二叉树条件
        return true;
    }
}
